The invention disclosed herein relates generally to systems and methods for determining the topology of computer networks. More particularly, the present invention relates to methods for identifying and resolving missing devices in a topology of a computer network.
There are many existing systems for determining the topology features of a network. Topology is generally concerned with the physical interconnections between devices in a computer network. This is referred to as Layer 2 or the Data Link Layer, which is one of several layers comprising the multi-layered communication model known as Open Systems Interconnection (OSI). In a network, devices may redirect data messages at the layer 2 level using the destination Media Access Control Address to determine where to direct the message. The Data Link Layer ensures that an initial connection has been achieved between devices, divides output data into frames, and handles the acknowledgements from a receiver that the data arrived successfully. A switch is one example of a Layer 2 device.
Examining the address of neighboring nodes on a network may also be used to derive the topology features of a network. This is referred to as Layer 3, or the Network Layer, of the OSI model. Layer 3 is concerned with knowing the address of the neighboring nodes in a network, selecting routes based thereupon, and providing quality of service. A router is an example of a Layer 3 device, although some newer switches perform Layer 3 functions, and the Internet Protocol address is a Layer 3 address.
Examining the devices attached to each port of a device derives Layer 2 topology. FIG. 1 presents the Layer 2 topology of an exemplary network comprised of devices A 102, B 104, C 108, and D 106. Each device on the network (link domain) has two ports, each connected to a port on another device. Layer 2 devices are identified by a Media Access Control (MAC) address. The MAC address is imprinted on a network controller at the point of manufacture, and is associated with each port on a device. These physical interconnections, identified by source and destination MAC addresses, are recorded in a master link table the stores the source name, source port, destination name, and destination port. Table 1, which follows, presents the master link table for the network presented in FIG. 1:
TABLE 1Source nameSource portDestination nameDestination portA1B1A2D1B1A1B2C2C2B2C1D2D2C1D1A2Using the master link table presented above in Table 1, existing topology systems are capable of constructing a graphical representation of the network's topology (FIG. 1). Similar techniques are also available for deriving network topology through utilizing Layer 3 data.
While it is know in the art to obtain the topology features using Layer 2 and Layer 3 addresses, existing topology systems and methods fail to account for situations where knowledge of a network is missing. This can occur for a variety of reasons. For example, incorrectly configuring the security settings of a device may result in the device not responding to a variety of requests. Likewise, the device may not support the discovery mechanism being employed by the topographer or the device may be owned by a third party who has denied access to the discovery features of the device.
Systems that do not recognize the existence of missing devices when deriving the topology of a network result in topologies containing anomalies. By identifying when there are missing devices on a network and removing the anomalies associated with them, systems that subsequently use the topology can be simplified. Without accounting for anomalies, subsequent system must necessarily be more complex as they must provide for business logic to handle the exceptional cases caused by the anomalies. Furthermore, by identifying missing devices it is possible to alert a user to the issue, enabling the problem to be manually addressed if the situation requires it.
An exemplary network topology containing anomalies, as discussed above, is presented in FIG. 2. The network comprises a plurality of devices, 202, 204, 206, 208, 210, 212, 214. Each line represents the physical interconnections between ports of the devices, e.g., between 210 and 214 and between 210 and 208. An anomaly is generated when a device 202 is depicted based on retrieved or generated topology data as being physically connected to two distinct devices, 204 and 206, over a single port. The topology may be broken down into sub-topologies 216 wherein each sub-topology represents a domain of Layer 2 devices. By limiting the scope of analysis to a sub-topology, or interconnection between two or more sup-topologies, the task of identifying missing devices is simplified.
Although a number of techniques have been developed to determine devices missing from a network topology, they all have significant drawbacks. U.S. Pat. No. 5,708,772, entitled “Network Topology Determination by Dissecting Unitary Connections and Detecting Non-responsive Nodes”, presents a solution to determine missing Layer 2 devices whereby every Layer 2 device that traverses an unknown device needs to be aware of every other device connected to the unknown device. For example, assume the following topology presented in Table 2, comprising devices A, B, C, and D, where device B is an unknown device:
TABLE 2According to the system and method described, device A must be aware of devices C and D. Similarly, device D must be aware of devices A and C. Furthermore, transitive links must be identified and resolved in order for the system and method to function properly, e.g., if device C is further connected to device E, then device A must be aware of device E. This, however, is not always the case, which has the potential to result in erroneous topologies being generated.
Another solution to the problem has been proposed by U.S. Pat. No. 5,926,462, entitled “Method of Determining Topology Features of a Network of Objects Which Compares the Similarity of the Traffic Sequences/Volumes of a Pair of Devices”. According to this method, topology is derived by analyzing traffic profiles; changes in profiles reflect changes in topology. Unfortunately, this method requires constant monitoring of traffic patterns over an extended period of time, unnecessarily consuming network resources.
There is thus a need for a system and method to identify and resolve missing devices in a network topology. The invention described herein adopts an approach of identifying and resolving the anomalies by inserting a “virtual device” into the topology to represent the missing device. The system and method of the present invention further reduces the number of such virtual devices and ensures that no anomalies exist between the virtual devices themselves.